基于随机序列统计特性的伪随机序列生成方法

doi:10.11 959/j.issn.2096-109x.2017.00125

Abstract

Abstract:

There are some problems existing in pseudo-random sequence generating methods, such as the weaker proportionality, bad run length characteristic, etc. Hence, based on the SimiHam algorithm in Knight's tour problem, a pseudo-random sequences generating method was proposed according to the statistical properties of random se-quence. First, set runs value 0 and 1 in different length for the grids in chessboard, and then scan the chessboard with Hamilton cycles which are generated by SemiHam algorithm in Knight's tour problem, At last extract run length values of 0 and 1 and get the pseudo-random sequences. Experimental results show that the pseudo-random se-quence generated by the proposed algorithm satisfies the statistical properties of a random sequence and has better randomness.

Key words: pseudo-random sequence, statistical properties of a random sequence, SemiHam algorithm, NIST SP800-22 random test

CLC Number:

TN919.81

Sen BAI,Long-fu ZHOU,Hui GUO,Bing YAN. Method to generate the pseudo random sequence based on the statistical properties[J]. Chinese Journal of Network and Information Security, 2017, 3(1): 31-38.

Figures/Tables 12

游程长度/	游程占总游程的比例
l=1	$\frac{1}{2}$
l=2	$\frac{1}{4}$
l=3	$\frac{1}{8}$
l=4	$\frac{1}{16}$
l=5	$\frac{1}{32}$

References 18

[1]	吴资玉，韩庆文，通信原理[M]. 北京: 电子工业出版社， 2008: 316-317.
	WU Z Y , HAN Q W . Principles of communications[M]. Beijing: Publishing House of Electronics Industry. 2008: 316-317.
[2]	HUANG X , YE G . An image encryption algorithm based on hy-per-chaos and DNA sequence[J]. Multimedia Tools and Applica-tions, 2014, 72 (1): 57-70.
[3]	雷雄俊，刘光斌 . GPS伪随机序列的构成及应用分析[J]. 光通信研究， 2010, 21 (6): 64-67.
	LEI H J , LIU G B . Architecture and applications of GPS pseudo-random sequence[J]. Study on Optical Communications, 2010, 21 (6): 64-67.
[4]	AHMED Z , CANCES J P , MEGHDADI V . MEGHDADI V. Cryptographic spread spectrum relay communication[C]// Next Generation Mobile Appli-cations, Services and Technologies. 2008: 588-591.
[5]	张群英，方广有 . 伪随机序列编码脉冲信号在探地雷达中的应用研究[J]. 电子与信息学报， 2012, 33 (2): 424-428.
	ZHANG Q Y , FANG G Y . The study of pseudo random sequence's application to GPR[J]. Journal of Electronics＆Information Tech-nology, 2012, 33 (2): 424-428
[6]	杜小妮 . 伪随机序列的构造及其随机性分析[D]. 陕西: 西安电子科技大学， 2008.
	DU X N . The construction and randomness analysis of pseudo ran-dom sequence[D]. Shaanxi: Xidian University, 2008.
[7]	张丽姣，闵乐泉，韩双霜 . 二维新混沌系统和伪随机数生成器的设计[J]. 计算机工程与设计， 2014, 35 (4): 1178-1182.
	ZHANG L J , MIN L Q , HAN S S . Design of 2-dimensional novel chaotic system and pseudo-random number generator[J]. Computer Engineering and Design, 2014, 35 (4): 1178-1182.
[8]	孙克辉，叶正伟，贺少波 . 混沌伪随机序列发生器的FPGA设计与实现[J]. 计算机应用与软件， 2014, 6 (12): 3-7.
	SUN K H , YE Z W , HE S B , Design and implementation of chaotic pseudo-random sequence generator using FPGA[J]. Computer Ap-plications and Software, 2014, 6 (12): 3-7.
[9]	李家标，曾以成，陈仕必，等. 改进型Henon映射生成混沌伪随机序列及性能分析[J]. 物理学报， 2011, 60 (6): 126-130.
	LI J B , ZENG Y C , CHEN S B , Modified Hénon map generated chaotic pseudorandom-bit sequences and performance analysis[J]. Acta Physica Sinica, 2011, 60 (6): 126-130.
[10]	叶珍，臧鸿雁 . 基于混沌系统的量化方法及伪随机性研究[J]. 计算机应用研究， 2014, 31 (12): 3719-3721.
	YE Z , ZANG H Y . Research of quantization methods and pseudo-randomness based on chaotic systems[J]. Application Research of Computers, 2014, 31 (12): 3719-3721.
[11]	花文昭，韩文报 . 基于椭圆曲线的二元伪随机序列构造与分析[J]. 计算机工程， 2012, 38 (18): 100-102.
	HUA W Z , HAN W B . Construction and analysis of binary pseu-dorandom sequences based on elliptic curve[J]. Computer Engi-neering, 2012, 38 (18): 100-102.
[12]	JESSA M , JAWORSKI M . Producing secure pseudorandom se-quences with combined multiplicative congruential generators[C]// Systems, Signals and Image Processing (IWSSIP). 2012: 160-163.
[13]	NIVASCH G . Experimental results on hamiltonian-cycle-finding algorithms[R]. Weizman Institute, Israel, 2003.
[14]	柏森，杨晓帆 . 求马步图 Hamilton 圈的最优算法[J]. 计算机工程与科学， 2000, 22 (2): 8-11.
	BAI S , YANG X F . An optimal algorithm for searching a Hamilton cycle of the knight-tour's problem[J]. Computer Engineering＆Science, 2000, 22 (2): 8-11.
[15]	DEMAIO J . Which chessboards have a closed knight's tour within the cube[J]. Journal of Combinatorics, 2007, 14 (2): 1-9.
[16]	BAI S , LIAO X F , QU X H , et al. Generalized knight's tour prob-lem and its solutions algorithm[C]// 2006 International Conference on Computational Intelligence and Security. 2006: 570-573.
[17]	SIVAKUMAR T , VENKATESAN R . A novel approach for image encryption using dynamic scan pattern[J]. IAENG International Journal of Computer Science, 2014, 41 (2): 91-101.
[18]	RUKHIN A , SOTO J , NECHVATAL J , et al. A statistical test suite for random and pseudorandom number generators for cryptographic applications[R]. Booz-Allen and Hamilton Inc Mclean Va, 2001.

Metrics

Recommended 0

No Suggested Reading articles found!

棋盘大小	0的数量/个	1的数量/个	1占的比例
20×20	397	397	50％
20×35	694	694	50％
25×55	1 369	1 368	49.98％
40×10	397	397	50％

测试项目	1组测试值	2组测试值	3组测试值	4组测试值	5组测试值
Frequency Test	1.000 0	1.000 0	1.000 0	1.000 0	1.000 0
Frequency Test within a Block	0.986 7	0.777 3	0.390 0	0.956 7	0.876 1
Runs Test	0.747 4	0.747 4	0.747 4	0.747 4	0.747 4
Test for the Longest of Ones in a Block	0.035 4	0.870 7	0.972 7	0.576 8	0.968 4
Discrete Fourier Transform Test	0.072 2	0.506 0	0.748 8	0.247 0	0.506 0
Linear Complexity Test	0.808 8	0.423 2	0.000 04	0.985 6	0.676 7
	0.709 4	0.995 3	0.499 0	0.355 3	0.865 9
Serial Test
	0.742 1	0.998 8	0.096 5	0.742 1	0.941 8
Approximate Entropy Test	0.780 4	0.232 0	0.332 8	0.555 6	0.459 7
	0.878 4	0.785 7	0.376 7	0.810 1	0.934 9
Cumulative Sums Test
	0.878 4	0.785 7	0.376 7	0.810 1	0.934 9
OverlappingTemplate	0.488 4	0.886 6	0.886 6	0.488 4	0.488 4
Rank	0.291 9	0.693 7	0.291 9	0.693 7	0.291 9

测试项目	本文算法	文献[ 10 ]算法
Frequency Test	1.000	0.712
Frequency Test within a Block	0.797	0.699
Runs Test	0.747	0.259
Test for the Longest of Ones in a
	0.685	0.284
Block
Discrete Fourier Transform Test	0.416	0.266
Linear Complexity Test	0.579	0.924
	0.685	0.584
Serial Test
	0.704	0.682
Approximate Entropy Test	0.472	0.54
	0.757	0.719
Cumulative Sums Test
	0.757	0.728

Method to generate the pseudo random sequence based on the statistical properties

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 18

Related Articles 0

Metrics

Recommended 0

棋盘大小	l=1	l=2	l=3	l=4	l=5	l=6	l=7	l=8	l=9
20×20	200	100	50	26	12	6	4	2	-
20×35	350	176	88	44	22	10	6	2	2